package com.base.dataStructure.Tree.redblacktree;

import com.base.dataStructure.BlockingQueue.BlockingQueue;

import java.util.function.BinaryOperator;

import static com.base.dataStructure.Tree.redblacktree.RedBlackTree.Color.BLACK;
import static com.base.dataStructure.Tree.redblacktree.RedBlackTree.Color.RED;

/**
 * @Author: hdhao
 * @Create: 2023/4/9 - 20:47
 * @Version: v1.0
 */
//红黑树
@SuppressWarnings("all")
public class RedBlackTree {
    enum Color{
        RED, BLACK;
    }
    private Node root;
    private static class Node{
        int key;
        Object value;
        Node left;
        Node right;
        Node parent;    //当前节点的父节点
        Color color = RED; //颜色

        public Node(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        //是否是左孩子
        boolean isLeftChild() {
            return parent != null && parent.left == this;
        }

        Node uncle() {
            if (parent == null || parent.parent == null) {
                return null;
            }
            if (parent.isLeftChild()){
                return parent.parent.right;
            } else {
                return parent.parent.left;
            }
        }

        Node brother(){
            if (parent == null){
                return null;
            }
            if (this.isLeftChild()){
                return parent.right;
            } else {
                return parent.left;
            }
        }
    }
    boolean isRed(Node node){
        return node != null && node.color == RED;
    }

    boolean isBlack(Node node){
        return !isRed(node);
    }

    //右旋 1.parent的处理 2.旋转后新根的父子关系
    public void rightRotate(Node pink) {
        Node parent = pink.parent;
        Node yellow = pink.left;
        Node green = yellow.right;
        if (green != null) {
            green.parent = pink;
        }
        yellow.right = pink;
        yellow.parent = parent;
        pink.left = green;
        pink.parent = yellow;
        if (parent == null) {
            root = yellow;
        } else if (parent.left == pink) {
            parent.left = yellow;
        } else {
            parent.right = yellow;
        }
    }
    //左旋
    public void leftRotate(Node node) {

    }
    /*
        新增或更新
        正常新增,遇到红红不平衡进行调整
     */
    public void put(int key, Object value) {
        Node p = root;
        Node parent = null;
        while (p != null) {
            parent = p;
            if (key < p.key) {
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            } else {
                p.value = value;//更新
                return;
            }
        }
        Node inserted = new Node(key, value);
        if (parent == null) {
            root = inserted;
        } else if (key < parent.key) {
            parent.left = inserted;
            inserted.parent = parent;
        } else {
            parent.right = inserted;
            inserted.parent = parent;
        }
        fixRedRed(inserted);
    }
    //调整双红的情况
    void fixRedRed(Node x) {
        //case1 插入节点是根节点,变黑即可
        if (x == root) {
            x.color = BLACK;
        }
        //case2 插入节点的父节点是黑色,无需调整
        if (isBlack(x.parent)) {
            return;
        }
        //插入节点的父亲是红色,触发红红相邻
        //case3 叔叔为红色
        /*
            1.父亲变为黑色,为了保证黑色平衡,连带的叔叔也变为黑色
            2.祖父如果是黑色不变,会造成这棵子树黑色过多,因此祖父节点变为红色
            3.祖父如果变成红色,可能会接着触发红红相邻,因此将对祖父节点进行递归调整
         */
        Node parent = x.parent;
        Node uncle = x.uncle();
        Node grandParent = parent.parent;
        if (isRed(uncle)) {
            parent.color = BLACK;
            uncle.color = BLACK;
            grandParent.color = RED;
            fixRedRed(grandParent);
            return;
        }
        //case4 叔叔为黑色
        /*
            1.父亲是左孩子,插入节点也是左孩子,此时LL不平衡
            1.父亲是左孩子,插入节点也是右孩子,此时LR不平衡
            1.父亲是右孩子,插入节点也是右孩子,此时RR不平衡
            1.父亲是右孩子,插入节点也是左孩子,此时RL不平衡
         */
        if (parent.isLeftChild() && x.isLeftChild()) { //LL不平衡
            parent.color = BLACK;
            grandParent.color = RED;
            rightRotate(grandParent);
        } else if (parent.isLeftChild() && !x.isLeftChild()) {//LR不平衡
            leftRotate(parent);
            x.color = BLACK;
            grandParent.color = RED;
            rightRotate(grandParent);
        } else if (!parent.isLeftChild() && !x.isLeftChild()) {//RR不平衡
            parent.color = BLACK;
            grandParent.color = RED;
            leftRotate(grandParent);
        } else { //RL不平衡
            rightRotate(parent);
            x.color = BLACK;
            grandParent.color = RED;
            leftRotate(grandParent);
        }
    }
    /*
        删除
        正常删,会用到李代桃僵技巧,遇到黑黑不平衡进行调整
     */
    public void remove(int key) {
        Node deleted = find(key);
        if (deleted == null) {
            return;
        }
        doRemove(deleted);
    }

    private void fixDoubleBlack(Node node) {

    }

    private void doRemove(Node deleted) {
        Node replaced = findReplaced(deleted);
        Node parent = deleted.parent;
        if (replaced == null) { //没有孩子
            //case 1
            if (deleted == root) {
                root = null;
            } else {
                if (isBlack(deleted)) {
                    //复杂调整
                    fixDoubleBlack(deleted);
                } else {
                    //红色叶子,无需任何处理
                }
                if (parent.isLeftChild()) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
                deleted.parent = null;
            }
            return;
        }
        //有一个孩子
        if (deleted.left == null || deleted.right == null) {
            if (deleted == root) {
                root.key = replaced.key;
                root.value = replaced.value;
                root.left = null;
                root.right = null;
            } else {
                if (deleted.isLeftChild()) {
                    parent.left = replaced;
                } else {
                    parent.right = replaced;
                }
                replaced.parent = parent;
                deleted.left = deleted.right = deleted.parent = null;
                if (isBlack(deleted) && isBlack(replaced)) {
                    //复杂处理
                    fixDoubleBlack(replaced);
                } else {
                    replaced.color = BLACK;
                }
            }
            return;
        }
        //有两个孩子 =>有一个孩子或没有孩子
        int t = deleted.key;
        deleted.key = replaced.key;
        replaced.key = t;

        Object v = deleted.value;
        deleted.value = replaced.value;
        replaced.value = v;
        doRemove(replaced);
    }

    //查找删除节点
    Node find(int key) {
        Node p = root;
        while (p != null) {
            if (key < p.key) {
                p = p.left;
            } else if(p.key < key) {
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }
    //查找剩余节点
    Node findReplaced(Node deleted) {
        if (deleted.left == null && deleted.right == null) {
            return null;
        }
        if (deleted.left == null) {
            return deleted.right;
        }
        if (deleted.right == null) {
            return deleted.left;
        }
        Node s = deleted.right;
        while (s.left != null) {
            s = s.left;
        }
        return s;
    }

}
